Large scale network services may be implemented using multiple discrete server instances in an effort to increase robustness, capacity, and performance. These network services may be enhanced by scaling out the number of discrete server instances as opposed to scaling up. That is, it may be advantageous to have a large number of commodity server machines with minimal interaction between one another in comparison to a smaller number of powerful server machines. Scaling out along with reducing accumulated state information (e.g., an affinity between a task and a particular server instance because of cached data) may mitigate the overhead in adding new server instances or replacing failed server instances. Efficiency and proper task performance (e.g., a singleton task performed by a particular number of server instances) may be become an issue when introducing new server instances into an always on network service environment.